Zadanie Formuły (for)

Statystyki zadania
Liczba osob: 10
Liczba osob na 100 punktow: 5
Sredni wynik: 56

Formuły

Dostępna pamięć: 32 MB

Jak mawiają górale, są trzy rodzaje prawdy: święta prawda, tyż prawda i ... prawda. Najnowsze badania bajtockich logików potwierdzają to. Badają oni wyrażenia logiczne (formuły zdaniowe) o uproszczonej postaci nazywanej klauzulową. Postać klauzulowa wygląda następująco:

Formuły budujemy używając zmiennych logicznych x₁, x₂,..., x_n. Zmienne te mogą przyjmować wartości prawda lub fałsz.
Literał, to zmienna logiczna lub jej negacja, x_i lub $$ \neg$% WIDTH=15 HEIGHT=16$ x_i (dla 1 $$ \le$% WIDTH=16 HEIGHT=30$ i $$ \le$% WIDTH=16 HEIGHT=30$ n).
Klauzula, to koniunkcja literałów, np. x₄ $$ \wedge$% WIDTH=15 HEIGHT=16$ $$ \neg$% WIDTH=15 HEIGHT=16$ x₂ $$ \wedge$% WIDTH=15 HEIGHT=16$ x₃.
Formuła, to alternatywa klauzul, np. (x₁ $$ \wedge$% WIDTH=15 HEIGHT=16$ $$ \neg$% WIDTH=15 HEIGHT=16$ x₂) $$ \vee$% WIDTH=15 HEIGHT=16$ ( $$ \neg$% WIDTH=15 HEIGHT=16$ x₁ $$ \wedge$% WIDTH=15 HEIGHT=16$ x₃) $$ \vee$% WIDTH=15 HEIGHT=16$ ( $$ \neg$% WIDTH=15 HEIGHT=16$ x₃).

Wartość formuły zależy od konkretnych wartości zmiennych. Wartości zmiennych określa się za pomocą funkcji nazywanej wartościowaniem, postaci f : {1, 2,..., n} $$ \to$% WIDTH=20 HEIGHT=16$ {prawda,fałsz}, gdzie f (i) jest wartością nadawaną zmiennej x_i. Wszystkich możliwych wartościowań jest 2ⁿ. Dla konkretnego wartościowania, wartością danej formuły jest albo prawda albo fałsz.

Mówimy, że formuła jest prawdziwa, jeśli dla każdego wartościowania jej wartością jest prawda. Powiemy, że formuła jest fałszywa, jeżeli dla każdego wartościowania jej wartością jest fałsz. Często formuła nie jest ani prawdziwa, ani fałszywa, ale jej wartość zależy faktycznie od danego wartościowania. Prawdziwość formuły możemy określić jako ułamek (z zakresu od 0 do 1):

$$\displaystyle {\frac{{ \mbox{liczba wartościowań, dla których wartością formuły jest prawda} }}{{2^n}}}$% WIDTH=414 HEIGHT=51$

Liczba 1 odpowiada formułom prawdziwym, a 0 fałszywym.

Przykład

Formuła:

(x₁ $$\displaystyle \wedge$% WIDTH=15 HEIGHT=30$ $$\displaystyle \neg$% WIDTH=15 HEIGHT=30$ x₁) $$\displaystyle \vee$% WIDTH=15 HEIGHT=30$ ( $$\displaystyle \neg$% WIDTH=15 HEIGHT=30$ x₂ $$\displaystyle \wedge$% WIDTH=15 HEIGHT=30$ $$\displaystyle \neg$% WIDTH=15 HEIGHT=30$ x₃) $$\displaystyle \vee$% WIDTH=15 HEIGHT=30$ (x₃ $$\displaystyle \wedge$% WIDTH=15 HEIGHT=30$ x₂)

jest prawdziwa dla czterech spośród ośmiu możliwych wartościowań. Tak więc jest ona prawdziwa w połowie.

Zadanie

Dysponujesz 11 zestawami danych umieszczonymi w tym archiwum. Każdy zestaw jest zapisany w osobnym pliku: fork.in, gdzie k jest numerem zestawu ( 0 $$ \le$% WIDTH=16 HEIGHT=30$ k $$ \le$% WIDTH=16 HEIGHT=30$ 10). Plik for0.in zawiera dane zgodne z powyższym przykładem. Napisz program, który na wejściu otrzymuje dokładnie jedną liczbę całkowitą k ( 0 $$ \le$% WIDTH=16 HEIGHT=30$ k $$ \le$% WIDTH=16 HEIGHT=30$ 10) i wypisuje dokładnie jeden wiersz wyjścia, zawierający przybliżoną prawdziwość formuły podanej w k-tym zestawie danych. Prawdziwość powinna być wypisana w postaci ułamka dziesiętnego, obliczonego ze względną dokładnością 3%. To znaczy, jeśli prawdziwość formuły to p, a jej obliczone przybliżenie to p', to musi zachodzić | p' - p| $$ \le$% WIDTH=16 HEIGHT=30$ 0.03p.

Opis pojedynczego pliku wejściowego

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite n i m, 1 $$ \le$% WIDTH=16 HEIGHT=30$ n $$ \le$% WIDTH=16 HEIGHT=30$ 100, 1 $$ \le$% WIDTH=16 HEIGHT=30$ m $$ \le$% WIDTH=16 HEIGHT=30$ 100, oddzielone pojedynczym odstępem. Zmienne logiczne, które mogą pojawiać się w formule to x₁, x₂,..., x_n. Formuła składa się z m klauzul, opisanych w kolejnych m wierszach, po jednej w wierszu. Każdy z tych wierszy zawiera liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza z tych liczb, l, 1 $$ \le$% WIDTH=16 HEIGHT=30$ l $$ \le$% WIDTH=16 HEIGHT=30$ n, to liczba literałów tworzących klauzulę. Dalej w wierszu znajduje się l liczb całkowitych reprezentujących kolejne literały klauzuli. Są to liczby różne od zera, z zakresu od - n do n. Liczba i (dla 1 $$ \le$% WIDTH=16 HEIGHT=30$ i $$ \le$% WIDTH=16 HEIGHT=30$ n) reprezentuje x_i, a liczba - i reprezentuje $$ \neg$% WIDTH=15 HEIGHT=16$ x_i.

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

0.5

Uwaga

Akceptowanymi odpowiedziami do przykładowego testu są również: 0.485, 0.498, 0.51, 0.515.

Autor zadania: Marcin Stefaniak.

<Wyślij rozwiązanie> [0/100]